home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 2003 August / MW 8 2003 CD1.iso / Inside Macworld / Product News / gimp-1.2.4.sit / gimp-1.2.4 / app / boundary.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-12-16  |  11.8 KB  |  523 lines
  1. /* The GIMP -- an image manipulation program
  2.  * Copyright (C) 1995 Spencer Kimball and Peter Mattis
  3.  *
  4.  * This program is free software; you can redistribute it and/or modify
  5.  * it under the terms of the GNU General Public License as published by
  6.  * the Free Software Foundation; either version 2 of the License, or
  7.  * (at your option) any later version.
  8.  *
  9.  * This program is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  * GNU General Public License for more details.
  13.  *
  14.  * You should have received a copy of the GNU General Public License
  15.  * along with this program; if not, write to the Free Software
  16.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17.  */
  18.  
  19. #include "config.h"
  20.  
  21. #include <string.h>
  22.  
  23. #include <glib.h>
  24.  
  25. #include "apptypes.h"
  26.  
  27. #include "appenv.h"
  28. #include "errors.h"
  29. #include "boundary.h"
  30. #include "tile.h"
  31.  
  32. /* half intensity for mask */
  33. #define HALF_WAY 127
  34.  
  35. /* BoundSeg array growth parameter */
  36. #define MAX_SEGS_INC  2048
  37.  
  38. /*  The array of vertical segments  */
  39. static int *      vert_segs = NULL;
  40.  
  41. /*  The array of segments  */
  42. static BoundSeg * tmp_segs = NULL;
  43. static int        num_segs = 0;
  44. static int        max_segs = 0;
  45.  
  46. /* static empty segment arrays */
  47. static int *      empty_segs_n = NULL;
  48. static int        num_empty_n = 0;
  49. static int *      empty_segs_c = NULL;
  50. static int        num_empty_c = 0;
  51. static int *      empty_segs_l = NULL;
  52. static int        num_empty_l = 0;
  53. static int        max_empty_segs = 0;
  54.  
  55. /* global state variables--improve parameter efficiency */
  56. static PixelRegion * cur_PR;
  57.  
  58.  
  59. /*  local function prototypes  */
  60. static void find_empty_segs (PixelRegion *, int, int *, int, int *,
  61.                  BoundaryType, int, int, int, int);
  62. static void make_seg (int, int, int, int, int);
  63. static void allocate_vert_segs (void);
  64. static void allocate_empty_segs (void);
  65. static void process_horiz_seg (int, int, int, int, int);
  66. static void make_horiz_segs (int, int, int, int *, int, int);
  67. static void generate_boundary (BoundaryType, int, int, int, int);
  68.  
  69. /*  Function definitions  */
  70.  
  71. static void
  72. find_empty_segs (PixelRegion  *maskPR,
  73.          int           scanline,
  74.          int           empty_segs[],
  75.          int           max_empty,
  76.          int          *num_empty,
  77.          BoundaryType  type,
  78.          int           x1,
  79.          int           y1,
  80.          int           x2,
  81.          int           y2)
  82. {
  83.   unsigned char *data;
  84.   int x;
  85.   int start, end;
  86.   int val, last;
  87.   int tilex;
  88.   Tile *tile = NULL;
  89.   int endx, l_num_empty, dstep = 0;
  90.  
  91.  
  92.   data  = NULL;
  93.   start = 0;
  94.   end   = 0;
  95.  
  96.   *num_empty = 0;
  97.  
  98.   if (scanline < maskPR->y || scanline >= (maskPR->y + maskPR->h))
  99.     {
  100.       empty_segs[(*num_empty)++] = 0;
  101.       empty_segs[(*num_empty)++] = G_MAXINT;
  102.       return;
  103.     }
  104.  
  105.   if (type == WithinBounds)
  106.     {
  107.       if (scanline < y1 || scanline >= y2)
  108.     {
  109.       empty_segs[(*num_empty)++] = 0;
  110.       empty_segs[(*num_empty)++] = G_MAXINT;
  111.       return;
  112.     }
  113.  
  114.       start = x1;
  115.       end = x2;
  116.     }
  117.   else if (type == IgnoreBounds)
  118.     {
  119.       start = maskPR->x;
  120.       end = maskPR->x + maskPR->w;
  121.       if (scanline < y1 || scanline >= y2)
  122.     x2 = -1;
  123.     }
  124.  
  125.   tilex = -1;
  126.   empty_segs[(*num_empty)++] = 0;
  127.   last = -1;
  128.  
  129.   l_num_empty = *num_empty;
  130.  
  131.   for (x = start; x < end;)
  132.     {
  133.       /*  Check to see if we must advance to next tile  */
  134.       if ((x / TILE_WIDTH) != tilex)
  135.     {
  136.       if (tile)
  137.         tile_release (tile, FALSE);
  138.       tile = tile_manager_get_tile (maskPR->tiles, x, scanline, TRUE, FALSE);
  139.       data = (unsigned char*)tile_data_pointer (tile, x % TILE_WIDTH, scanline % TILE_HEIGHT) + (tile_bpp(tile) - 1);
  140.  
  141.       tilex = x / TILE_WIDTH;
  142.       dstep = tile_bpp(tile);
  143.     }
  144.       endx = x + (TILE_WIDTH - (x%TILE_WIDTH));
  145.       endx = MIN (end, endx);
  146.       if (type == IgnoreBounds && (endx > x1 || x < x2))
  147.     for (; x < endx; x++)
  148.     {
  149.       if (*data > HALF_WAY)
  150.         if (x >= x1 && x < x2)
  151.           val = -1;
  152.         else
  153.           val = 1;
  154.       else
  155.         val = -1;
  156.  
  157.       data += dstep;
  158.  
  159.       if (last != val)
  160.         empty_segs[l_num_empty++] = x;
  161.  
  162.       last = val;
  163.     }
  164.       else
  165.     for (; x < endx; x++)
  166.     {
  167.       if (*data > HALF_WAY)
  168.         val = 1;
  169.       else
  170.         val = -1;
  171.  
  172.       data += dstep;
  173.  
  174.       if (last != val)
  175.         empty_segs[l_num_empty++] = x;
  176.  
  177.       last = val;
  178.     }
  179.  
  180.     }
  181.   *num_empty = l_num_empty;
  182.  
  183.   if (last > 0)
  184.     empty_segs[(*num_empty)++] = x;
  185.  
  186.   empty_segs[(*num_empty)++] = G_MAXINT;
  187.  
  188.   if (tile)
  189.     tile_release (tile, FALSE);
  190. }
  191.  
  192.  
  193. static void
  194. make_seg (int x1,
  195.       int y1,
  196.       int x2,
  197.       int y2,
  198.       int open)
  199. {
  200.   if (num_segs >= max_segs)
  201.     {
  202.       max_segs += MAX_SEGS_INC;
  203.  
  204.       tmp_segs = (BoundSeg *) g_realloc ((void *) tmp_segs,
  205.                     sizeof (BoundSeg) * max_segs);
  206.  
  207.       if (!tmp_segs)
  208.     gimp_fatal_error ("make_seg(): Unable to reallocate segments array for mask boundary.");
  209.     }
  210.  
  211.   tmp_segs[num_segs].x1 = x1;
  212.   tmp_segs[num_segs].y1 = y1;
  213.   tmp_segs[num_segs].x2 = x2;
  214.   tmp_segs[num_segs].y2 = y2;
  215.   tmp_segs[num_segs].open = open;
  216.   num_segs ++;
  217. }
  218.  
  219.  
  220. static void
  221. allocate_vert_segs (void)
  222. {
  223.   int i;
  224.  
  225.   /*  allocate and initialize the vert_segs array  */
  226.   vert_segs = (int *) g_realloc ((void *) vert_segs, (cur_PR->w + cur_PR->x + 1) * sizeof (int));
  227.  
  228.   for (i = 0; i <= (cur_PR->w + cur_PR->x); i++)
  229.     vert_segs[i] = -1;
  230. }
  231.  
  232.  
  233. static void
  234. allocate_empty_segs (void)
  235. {
  236.   int need_num_segs;
  237.  
  238.   /*  find the maximum possible number of empty segments given the current mask  */
  239.   need_num_segs = cur_PR->w + 3;
  240.  
  241.   if (need_num_segs > max_empty_segs)
  242.     {
  243.       max_empty_segs = need_num_segs;
  244.  
  245.       empty_segs_n = (int *) g_realloc (empty_segs_n, sizeof (int) * max_empty_segs);
  246.       empty_segs_c = (int *) g_realloc (empty_segs_c, sizeof (int) * max_empty_segs);
  247.       empty_segs_l = (int *) g_realloc (empty_segs_l, sizeof (int) * max_empty_segs);
  248.  
  249.       if (!empty_segs_n || !empty_segs_l || !empty_segs_c)
  250.     gimp_fatal_error ("allocate_empty_segs(): Unable to reallocate empty segments array for mask boundary.");
  251.     }
  252. }
  253.  
  254.  
  255. static void
  256. process_horiz_seg (int x1,
  257.            int y1,
  258.            int x2,
  259.            int y2,
  260.            int open)
  261. {
  262.   /*  This procedure accounts for any vertical segments that must be
  263.       drawn to close in the horizontal segments.                     */
  264.  
  265.   if (vert_segs[x1] >= 0)
  266.     {
  267.       make_seg (x1, vert_segs[x1], x1, y1, !open);
  268.       vert_segs[x1] = -1;
  269.     }
  270.   else
  271.     vert_segs[x1] = y1;
  272.  
  273.   if (vert_segs[x2] >= 0)
  274.     {
  275.       make_seg (x2, vert_segs[x2], x2, y2, open);
  276.       vert_segs[x2] = -1;
  277.     }
  278.   else
  279.     vert_segs[x2] = y2;
  280.  
  281.   make_seg (x1, y1, x2, y2, open);
  282. }
  283.  
  284.  
  285. static void
  286. make_horiz_segs (int start,
  287.          int end,
  288.          int scanline,
  289.          int empty[],
  290.          int num_empty,
  291.          int top)
  292. {
  293.   int empty_index;
  294.   int e_s, e_e;    /* empty segment start and end values */
  295.  
  296.   for (empty_index = 0; empty_index < num_empty; empty_index += 2)
  297.     {
  298.       e_s = *empty++;
  299.       e_e = *empty++;
  300.       if (e_s <= start && e_e >= end)
  301.     process_horiz_seg (start, scanline, end, scanline, top);
  302.       else if ((e_s > start && e_s < end) ||
  303.            (e_e < end && e_e > start))
  304.     process_horiz_seg (MAX (e_s, start), scanline,
  305.                MIN (e_e, end), scanline, top);
  306.     }
  307. }
  308.  
  309.  
  310. static void
  311. generate_boundary (BoundaryType type,
  312.            int          x1,
  313.            int          y1,
  314.            int          x2,
  315.            int          y2)
  316. {
  317.   int scanline;
  318.   int i;
  319.   int start, end;
  320.   int * tmp_segs;
  321.  
  322.   start = 0;
  323.   end   = 0;
  324.  
  325.   /*  array for determining the vertical line segments which must be drawn  */
  326.   allocate_vert_segs ();
  327.  
  328.   /*  make sure there is enough space for the empty segment array  */
  329.   allocate_empty_segs ();
  330.  
  331.   num_segs = 0;
  332.  
  333.   if (type == WithinBounds)
  334.     {
  335.       start = y1;
  336.       end = y2;
  337.     }
  338.   else if (type == IgnoreBounds)
  339.     {
  340.       start = cur_PR->y;
  341.       end = cur_PR->y + cur_PR->h;
  342.     }
  343.  
  344.   /*  Find the empty segments for the previous and current scanlines  */
  345.   find_empty_segs (cur_PR, start - 1, empty_segs_l,
  346.            max_empty_segs, &num_empty_l,
  347.            type, x1, y1, x2, y2);
  348.   find_empty_segs (cur_PR, start, empty_segs_c,
  349.            max_empty_segs, &num_empty_c,
  350.            type, x1, y1, x2, y2);
  351.  
  352.   for (scanline = start; scanline < end; scanline++)
  353.     {
  354.       /*  find the empty segment list for the next scanline  */
  355.       find_empty_segs (cur_PR, scanline + 1, empty_segs_n,
  356.                max_empty_segs, &num_empty_n,
  357.                type, x1, y1, x2, y2);
  358.  
  359.       /*  process the segments on the current scanline  */
  360.       for (i = 1; i < num_empty_c - 1; i += 2)
  361.     {
  362.       make_horiz_segs (empty_segs_c [i], empty_segs_c [i+1],
  363.                scanline, empty_segs_l, num_empty_l, 1);
  364.       make_horiz_segs (empty_segs_c [i], empty_segs_c [i+1],
  365.                scanline+1, empty_segs_n, num_empty_n, 0);
  366.     }
  367.  
  368.       /*  get the next scanline of empty segments, swap others  */
  369.       tmp_segs = empty_segs_l;
  370.       empty_segs_l = empty_segs_c;
  371.       num_empty_l = num_empty_c;
  372.       empty_segs_c = empty_segs_n;
  373.       num_empty_c = num_empty_n;
  374.       empty_segs_n = tmp_segs;
  375.     }
  376. }
  377.  
  378.  
  379. BoundSeg *
  380. find_mask_boundary (PixelRegion  *maskPR,
  381.             int          *num_elems,
  382.             BoundaryType  type,
  383.             int           x1,
  384.             int           y1,
  385.             int           x2,
  386.             int           y2)
  387. {
  388.   BoundSeg * new_segs = NULL;
  389.  
  390.   /*  The mask paramater can be any PixelRegion.  If the region
  391.    *  has more than 1 bytes/pixel, the last byte of each pixel is
  392.    *  used to determine the boundary outline.
  393.    */
  394.   cur_PR = maskPR;
  395.  
  396.   /*  Calculate the boundary  */
  397.   generate_boundary (type, x1, y1, x2, y2);
  398.  
  399.   /*  Set the number of X segments  */
  400.   *num_elems = num_segs;
  401.  
  402.   /*  Make a copy of the boundary  */
  403.   if (num_segs)
  404.     {
  405.       new_segs = (BoundSeg *) g_malloc (sizeof (BoundSeg) * num_segs);
  406.       memcpy (new_segs, tmp_segs, (sizeof (BoundSeg) * num_segs));
  407.     }
  408.  
  409.   /*  Return the new boundary  */
  410.   return new_segs;
  411. }
  412.  
  413.  
  414. /************************/
  415. /*  Sorting a Boundary  */
  416.  
  417. static int find_segment (BoundSeg *, int, int, int);
  418.  
  419. static int
  420. find_segment (BoundSeg *segs,
  421.           int       ns,
  422.           int       x,
  423.           int       y)
  424. {
  425.   int index;
  426.  
  427.   for (index = 0; index < ns; index++)
  428.     if (((segs[index].x1 == x && segs[index].y1 == y) || (segs[index].x2 == x && segs[index].y2 == y)) &&
  429.     segs[index].visited == FALSE)
  430.       return index;
  431.  
  432.   return -1;
  433. }
  434.  
  435.  
  436. BoundSeg *
  437. sort_boundary (BoundSeg *segs,
  438.            int       ns,
  439.            int      *num_groups)
  440. {
  441.   int i;
  442.   int index;
  443.   int x, y;
  444.   int startx, starty;
  445.   int empty = (num_segs == 0);
  446.   BoundSeg *new_segs;
  447.  
  448.   index = 0;
  449.   new_segs = NULL;
  450.  
  451.   for (i = 0; i < ns; i++)
  452.     segs[i].visited = FALSE;
  453.  
  454.   num_segs = 0;
  455.   *num_groups = 0;
  456.   while (! empty)
  457.     {
  458.       empty = TRUE;
  459.  
  460.       /*  find the index of a non-visited segment to start a group  */
  461.       for (i = 0; i < ns; i++)
  462.     if (segs[i].visited == FALSE)
  463.       {
  464.         index = i;
  465.         empty = FALSE;
  466.         i = ns;
  467.       }
  468.  
  469.       if (! empty)
  470.     {
  471.       make_seg (segs[index].x1, segs[index].y1,
  472.             segs[index].x2, segs[index].y2,
  473.             segs[index].open);
  474.       segs[index].visited = TRUE;
  475.  
  476.       startx = segs[index].x1;
  477.       starty = segs[index].y1;
  478.       x = segs[index].x2;
  479.       y = segs[index].y2;
  480.  
  481.       while ((index = find_segment (segs, ns, x, y)) != -1)
  482.         {
  483.           /*  make sure ordering is correct  */
  484.           if (x == segs[index].x1 && y == segs[index].y1)
  485.         {
  486.           make_seg (segs[index].x1, segs[index].y1,
  487.                 segs[index].x2, segs[index].y2,
  488.                 segs[index].open);
  489.           x = segs[index].x2;
  490.           y = segs[index].y2;
  491.         }
  492.           else
  493.         {
  494.           make_seg (segs[index].x2, segs[index].y2,
  495.                 segs[index].x1, segs[index].y1,
  496.                 segs[index].open);
  497.           x = segs[index].x1;
  498.           y = segs[index].y1;
  499.         }
  500.  
  501.           segs[index].visited = TRUE;
  502.         }
  503.  
  504.       if (x != startx || y != starty)
  505.         g_message ("sort_boundary(): Unconnected boundary group!");
  506.  
  507.       /*  Mark the end of a group  */
  508.       *num_groups = *num_groups + 1;
  509.       make_seg (-1, -1, -1, -1, 0);
  510.     }
  511.     }
  512.  
  513.   /*  Make a copy of the boundary  */
  514.   if (num_segs)
  515.     {
  516.       new_segs = (BoundSeg *) g_malloc (sizeof (BoundSeg) * num_segs);
  517.       memcpy (new_segs, tmp_segs, (sizeof (BoundSeg) * num_segs));
  518.     }
  519.  
  520.   /*  Return the new boundary  */
  521.   return new_segs;
  522. }
  523.